package com.lun.medium;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class FlattenBinaryTreeToLinkedList {
	
	//方法一：我写的，用到二叉树前序遍历模式的递归法
    public void flatten(TreeNode root) {
        flattenHelper(root);
    }
    
    private TreeNode flattenHelper(TreeNode node) {
    	if(node == null)
    		return null;
    	
    	TreeNode left = node.left; 
    	TreeNode right = node.right;
    	
    	node.left = null;
    	node.right = flattenHelper(left);
    	
    	TreeNode p = node;
    	while(p.right != null)
    		p = p.right;

    	p.right = flattenHelper(right);    	
    	return node;
    }
    
    //方法二：别人写的，很简洁
    private TreeNode prev = null;

    public void flatten2(TreeNode root) {
        if (root == null)
            return;
        flatten2(root.right);
        flatten2(root.left);
        root.right = prev;
        root.left = null;
        prev = root;
    }
    
    public void setPrevNull() {this.prev = null;}
    
    //方法三：别人写的，跟方法一的核心思想类似，区别在于本方法只用单一方法就搞定
    public void flatten3(TreeNode root) {
        if (root == null) return;
        
        TreeNode left = root.left;
        TreeNode right = root.right;
        
        root.left = null;
        
        flatten(left);
        flatten(right);
        
        root.right = left;
        TreeNode cur = root;
        while (cur.right != null) 
        	cur = cur.right;
        cur.right = right;
    }
    
    //方法四：别人写的，迭代法
    public void flatten4(TreeNode root) {
        if (root == null) return;
        LinkedList<TreeNode> stk = new LinkedList<>();
        stk.push(root);
        while (!stk.isEmpty()){
            TreeNode curr = stk.pop();
            if (curr.right!=null)  
                 stk.push(curr.right);
            if (curr.left!=null)  
                 stk.push(curr.left);
            if (!stk.isEmpty()) 
                 curr.right = stk.peek();
            curr.left = null;  // dont forget this!! 
        }
    }
    
}
